COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\section{Lots of \lisp\ functions to program.}
C00030 ENDMK
C⊗;
\section{Lots of \lisp\ functions to program.}
\sectlab{writinex}


	The following are descriptions of functions on lists and S-expressions.
You should write \lisp\ programs to compute these functions.  A description
of the form  ``$/foo/[/x\//]$ is true if and only if $\ldots$ ''
means your program should
return \qT\ in the case that $/foo/[/x\//]$ is true and \qNIL\ otherwise.
Write your solutions out in external form, if you wish, then
convert them to internal form and try them out in whatever LISP system
you have access to.   You should convince yourself by some informal
process of reasoning that your solutions are indeed correct.  You
will be asked to prove various facts about your programs more rigorously after you
have studied chapter \chapref{provin}.  This should encourage you to
write clean, understandable programs and document them carefully
so you will remember why you thought they were correct to begin with
and what tricks you may have employed.


	The problems are classified according to the intended interpretation
of the lists or S-expressions.  The classes include lists, S-expressions,
arithmetic expressions, polynomials, (finite) sets, permutations, trees, and graphs.
Each group begins with some simple problems (with one line solutions)
to get you going.  For the more complicated functions, you will find
that defining auxiliary functions is useful.  Towards the end the programs
may require a fair amount of thinking to get things organized correctly,
but none of the problems require really lengthy programs.
Pay attention to getting the trivial cases (e. g. when some of the arguments
are \qNIL\ or atomic or otherwise to be considered basic) correct.  It is 
in general important to understand the trivial cases in the computation
of a function.

	The observant reader will no doubt notice that some of these
functions are defined in later chapters.  Thus you will have some
cases where you can compare your solution to those given.   (References
to these definitions can be found in the function index.)
\medskip
\newcount\excount\excount=0
\def\startex{\medskip\advance\excount by 1\item{\the\excount.}}
\centerline{\bf Lists}
\nobreak
\startex $/samelength/[/u/,/v\//]$ tests whether the lists /u\// and /v\// 
have the same 
length.
$$/samelength/[|(A B C), (D E F)|] = \qT$$
$$/samelength/[|(A B C), (A C)|] = \qNIL$$
    Do not use any operations or tests on numbers to write your program.


\startex $/prup/[/u/,/v\//]$ 
is the list formed by pairing the corresponding elements
of the lists /u/ and /v/.  Thus

$$/prup/[|(X Y Z)|, |(1 A (FOO BAR))|] 
= |((X . 1) (Y . A) (Z FOO BAR))|.$$

\iffalse
\startex $/assoc-inverse/[/x/,/a\//]$ is a list of expressions associated with /x/ in 
the list of pairs (association-list) /a/.  Thus 
$$/assoc-inverse/[|(OR A B)|,|((P AND A C) (Q OR A B) (R IMPLIES C B) (S OR A B))|]
= |(Q S)|$$
$$/assoc-inverse/[|1|,|((X . 2) (Y . 0))|] = \qNIL\  .$$
\fi

\startex $/istail/[/u/,/v\//]$ is true if and only if the list /u/ is a tail of /v/.  
That is
when /cdr\//ing through /v/ you will eventually get to /u/.  

\startex $/commontail/[/u/,/v\//]$ is the longest common sublist of
/u/ and /v/ ending with the ends of the lists.  Thus

$$/commontail/[|(A B C D E)|,|(A C D E)|] = |(C D E)|.$$

\startex $/upto/[/u/,/v\//]$ 
when /u/ is a tail of /v/, is the list of elements of /v/ 
up to the point where /u/ begins.  Thus

$$/upto/[|(C D E)|,|(A B C D E)|] = |(A B)|.$$

\iffalse
\startex $/nth/[/u/,/n\//]$ is the /n\//th element of the list /u/.  

\startex $/nthpos/[/u/,/n\//]$ is the sublist of /u/ beginning with the /n\//th element.

\startex $/least/[/u\//]$ is the least integer in the list /u/ of integers.
\fi

\startex $/mapapp/[/f/,/u\//]$ appends together the lists obtained by applying /f/ 
to successive
elements of /u/.  

\startex $/mapchoose/[/p/,/u\//]$ forms a list of those elements of /u/ satisfying /p/.  

\startex $/partition/[/u/,/n\//]$ is the list of partitions of the list /u/ into
/n/ sublists $u↓1 \ldots u↓n$ such that $u↓1*u↓2*\ldots*u↓n=u$.  
If /n/ is greater than the length of /u/ then your program should return
an error message of some kind.
Thus 
$$/partition/[|(A B C)|,2]=|((A) (B C))((A B) (C)))|$$
   Write a program /testpart/ to test the result returned by /partition/.  
For each partition, /testpart/ should append together the lists $u↓i$
and check that the result is /u/.  

\medskip
\centerline{\bf S-expressions}
\nobreak
\iffalse % This function is the same as flip
\startex $/mirror/[/x\//]$ returns the mirror image of an S-expression /x/.  
Thus 
$$/mirror/[|((A.B).(C.D))|]=|((D.C).(B.A))|.$$
\fi
\iffalse % This function has already been presented in the section on unification
\startex $/occur/[/x/,/y\//]$ is true if and only if the atom /x/ occurs in the S-expression 
/y/.  For example

$$/occur/[|B|, |((A.B).C)|] = \qT.$$
\fi

\startex $/multiplicity/[/x/,/y\//]$ is the number of times the atom /x/ occurs in 
the S-expression /y/.  

\iffalse
\startex $/set-of-atoms/[/x\//]$ is a list without duplications of the atoms occurring in 
the S-expression /x/. 

\startex $/bag-of-atoms/[/x\//]$ is a list of all atoms that occur in the
S-expression /x/ paired with their multiplicities.
\fi
\item{}
        A path in an S-expression /x/ is a list of |A|'s and |D|'s such that you can
apply a succession of \qa's or \qd's to /x/ (according to whether the next list
element is |A| or |D|)  without trying to apply \qa\ or \qd\ to an atom.  We say
that the resulting subexpression is at the end of the path or that the path leads
to that subexpression.  Thus 
|(A D)| is a path in |((X . (Y . Z)) . F)|  but |(D A)| is not.
Also |(Y . Z)| is at the end of the path |(A D)| in |((X . (Y . Z)) . F)|.

\startex $/ispath/[/p/,/x\//]$ is true if and only if /p/ is a path in /x/.  

\startex $/depth/[/x\//]$ is the length of the longest path leading to an atom in the 
S-expression /x/.  
$$/depth/[|(((A . B) . C) . D|] = 3.$$

\item{} We say that an S-expression is balanced if it is an atom or if
$/depth/[\qa\ /x\//]$ and $/depth/[\qd\ /x\//]$ differ by at most 1
and \qa\ /x/ and \qd\ /x/ are both balanced.  

\startex $/balanced/[/x\//]$ is true if and only if the S-expression /x/ is balanced.

\startex $/balance/[/x\//]$ is balanced and has the same fringe as /x/.

\startex $/get/[/y/,/p\//]$ is the subexpression at the end of the path /p/ in the
S-expression /y/.  Thus
$$/get/[|(A ((B) C) (B))|,|(D A A)|] = |(B)|.$$

\startex $/point/[/x/,/y\//]$ is the path in the S-expression /y/
leading to the left-most 
occurrence of the S-expression /x/.  Thus
$$/point/[|(B)|,|(A ((B) C) (B))|] = |(D A A)|.$$

\startex $/allpoint/[/x/,/y\//]$ is a list of all paths /p/
such that $/get/[/y/,/p\//]=/x/$.  Thus
$$/allpoint/[|(B)|,|(A ((B) C) (B))|] = |((D A A) (D D A))|.$$

\startex $/commons/[/x\//]$ is a list of the subexpressions of the S-expression
/x/ that occur more than once in /x/, each followed by a list of the points 
(paths leading to the points) where it occurs. 

\iffalse
\startex Let /a/ be an association list pairing variables (atoms satisfying /isvar/)
their associated values (arbitrary S-expressions).  $/sublis/[/x/,/a\//] $
replaces every occurrence of a variable in the S-expressions /x/ with
its associated value in /a/.  This is done by ``simultaneous'' rather that
``sequential'' substitution so that if the value associated with a variable
happens to have a variable in it, that occurrence of the variable will 
remain in the result.

\startex Let /p/ be an S-expression with certain of the atoms
occurring /p/ regarded as variables, e.g. those atoms satisfying /isvar/
as in the previous problem.  For any S-expression /x/, if
there are substitutions for the variables in /p/  that
make /p/ and /x/ the same expression, then $/match/[/x/,/p\//]$ is a list of pairs
such that
$$/sublis/[/p/,/match/[/x/,/p\//] = /x/$$

    Otherwise, $/match/[/x/,/p\//] = |NO|$.  For example,
$$/match/[|(PLUS(TIMES X Y) Z)|,|(PLUS \&X \&Y)|] = |((\&X TIMES X Y) (\&Y . Z))|$$
where only the atoms |\&X| and |\&Y| are regarded as variables.
\fi
\medskip
\centerline{\bf Symbolic arithmetic and algebra}
\nobreak
\startex Let a polynomial in /x/ be represented by a list of its coefficients
in order of ascending powers of /x/.  Thus $x↑3+x+5$ is represented
by |(5 1 0 1)|.  
{\parskip=0pt
	\itemitem{\the\excount.1.} $/sum/[/u/,/v\//]$  is the sum
	\itemitem{\the\excount.2.} $/prod/[/u/,/v\//]$ is the product 
	\itemitem{\the\excount.3.} $/quot/[/u/,/v\//]$ is the quotient 
	\itemitem{\the\excount.4.} $/rem/[/u/,/v\//]$ is the remainder \hfil\break
of the polynomials /u/ and /v/ in the same notation.}


\startex  Consider arithmetic expressions as represented in this chapter.
Namely an expression is 
\ialign{\hbox to 32pt{\hfil #}\quad&#\hfil\cr
(i)&a number (satisfies /numberp/), \cr
(ii)&a variable (not a number and satisfies \qat),\cr
(iii)&a sum :$(|+|\qcons<{\rm list of expressions>})$, or\cr
(iv)&a product :$(|*|\qcons<{\rm list of expressions}>$.\cr
}
\item{}(For simplicity, assume the sum and product lists always have at least 
2 elements.)
\item{}
	The function /sop/ converts such expressions into sum of products
form, eg. the resulting expression is either a monomial 
or a sum of monomial terms which has the form 
$(|+|\qcons<{\rm list of monomials}>)$.
A monomial is either a number, a variable, or a product of the 
form $(|*|\qcons<{\rm list of numbers or variables}>)$.

	Try your simplifier on expressions returned by /diff/.
\medskip
\centerline{\bf Sets}
\nobreak
\startex Lists can be thought of as representing finite sets using the
the program $/member/[/x/,/u\//]$ defined earlier, to compute the membership
relation.   Write programs to compute the functions
union, $u\cup v$, intersection, $u\cap v$, and the set difference, $u\minus v$,
for lists /u/ and /v/ viewed as representing sets.  For example:
$$|(A B C)|\cup |(B C D) = (A B C D)|,$$
$$|(A B C)|\cap |(B C D) = (B C)|,    $$
and
$$|(A B C)|\minus |(B C D) = (A)|.      $$
\item{}
[Remark: 
There are a number of possible conventions for representing finite sets as lists.  
One is to require S-expressions representing elements of a set to occur in the 
representing list exactly once.   The other is to allow multiple occurrences
of an S-expression representing an element of the set.  You should decide
which convention you wish to adopt, and make sure your programs are consistent
with that convention]

\startex Suppose /x/ takes numbers as values and /u/ takes as
values lists of numbers in ascending order, e.g. |(2 4 7)|.  Write a
function $/insert/[/x/, /u\//]$ whose value is obtained from that of /u/ by
putting /x/ in /u/ in its proper place.   Thus
$$insert[|3|, |(2 4)|] = |(2 3 4)|,$$
and 
$$insert[|3|, |(2 3)|] = |(2 3 3)|.$$

\startex Write functions giving the union, intersection, and set
difference of ordered lists; the result is wanted as an ordered list.
\item{}
	Note that computing these functions of unordered lists takes
a number of comparisons proportional to the square of the number of
elements of a typical list, while for ordered lists, the number of
comparisons is proportional to the number of elements.

\startex Using /insert/, write a function /sort\// that transforms an
unordered list into an ordered list.

\startex Write a function /goodsort\// that sorts a list using a
number of comparisons proportional to $n\log n$, where /n/ is the
length of the list to be sorted.

\medskip
\centerline{\bf Permutations}
\nobreak
\startex $/rcycle/[/u\//]$ is obtained from the list /u/ by moving the
last element to the first position.  Thus
$$/rcycle/[|(A B C D)|] = |(D A B C)|.$$

\startex $/lcycle/[/u\//]$  is obtained from the list /u/ by moving the
first element to the last position.  Thus
$$/lcycle/[|(A B C D)|] = |(B C D A)|.$$ 

\item{}
        We can think of a permutation on /n/ objects as a function which maps
a list |(l1 l2 ... lN)| of /n/ distinct elements 
to a list containing the same elements in  a
different order.  Thus  |(3 4 1 2)| is a permutation of |(1 2 3 4)| and
|(FOO BAR BAZ)| is a permutation of |(BAR BAZ FOO)|.
The permutation itself can be represented as a list in several ways.
We describe two possible representations of a permutation /pi\//.
\item{}
	|REP1:| /pi\// is represented as a list of numbers |(j1 j2 ... jN)| 
which is itself a permutation of the list |(1 2 ... N)| and the result of 
applying such a permutation to a list /u/ of length /n/ is the list $u'$
where the $k$th element of $u'$ is the $jk$th element of /u/.  
Thus the permutation |(2 3 4 1)| applied to the list |(A B C D)|
is the list |(B C D A)|.  |(1 2 3 4)| is the identity permutation.
\item{}
	|REP2:| /pi\// is represented as a list of disjoint cycles, 
where a cycle is a a list of length at most /n/ of numbers between 1 and /n/ 
(with no two elements the same).  The permutation represented by such a
list of cycles is the permutation that results from applying each of the cycles.
(The order of application doesn't matter since the cycles are disjoint.)
The result of applying a cycle |(j1 j2 ... jk)| 
to a list /u/ of length /n/ is the list $u'$ where the element in position
/jm/ in $u'$ is the element in position $jm\minus 1$  in /u/ for $1≤m≤k$
(taking /j0/ to be /jk/).  Elements in positions not mentioned 
in the cycle are unchanged.
Thus the cycle  |(1 4 2)| applied to |(A B C D)| gives |(B D C A)|.
The empty list of cycles is the identity permutation in this representation.

\startex $isperm1[pi,n]$ ($isperm2[pi,n]$) is true just if the list /pi\// 
represents 
a permutation on /n/ objects according to |REP1| (|REP2|).

\startex $sameperm2[pi1,pi2]$ is true if and only if $pi1$ and $pi2$
represent the same
permutation.  (Note that the representation by |REP2| is not unique
while in |REP1| it is.)

\startex $rho12[pi]$ maps a list $pi$ representing a permutation according to
|REP1| to a list representing the same permutation according to |REP2|.
$rho21[u]$ is the inverse map.  

\startex $compose1[pi1,pi2]$ represents the permutation that results if $pi2$
is applied followed by $pi1$, all represented according to |REP1|.
$compose2[u,v]$ does the same but using |REP2|.

\startex $invert1[pi]$ ($invert2[pi]$) is the inverse to the permutation $pi$,
in |REP1| (|REP2|).  Thus $compose1[invert1[pi],pi]$ is the identity
permutation.
\item{}
        One way to solve these problems would be to write the
programs for one representation and use the transformations $rho12$ and $rho21$
to obtain those for the other representation.  However part of the
purpose of the exercise is to see how the different representations behave and
this solution would defeat that purpose.
\medskip
\centerline{\bf Trees}
\nobreak
\item{}
	 Consider a tree structure represented as a list in the following
way.  A leaf is any list of the form |(LEAF e)| where |e| is any
S-expression.  A tree is either a leaf, or a list of trees.

\startex  /leaves/[/t\//] is a list of all the leaves in the tree /t/, in the same
order as they appear in  the tree.  (Compare to /fringe/ for S-expressions.)

\startex  Let /leafval\// be an evaluation function on leaves.  (Assume /leafval\//
returns integers.)
$/bestleaf/[/t\//]$ is a leaf of /t\// having a maximal value according to 
/leafval/.
That is no other leaf of /t\// has a better value.

\startex $bestleaf1[t]$ is a leaf of $t$ 
of maximal value and among those of
the same value, $bestleaf1[t]$ has least depth (is closest to the root).
\medskip
\centerline{\bf Graphs}
\nobreak
\item{}
	Let /g\// be a directed graph represented as a list of lists as described
earlier in this chapter.

\startex $/isnext/[/u/,/v/,/g\//]$ is true if and only if /g\//
contains an edge from /u/ to /v/.  

\startex $/successors/[/u/,/g\//]$ is the list of vertices, /v/, in /g\//
such that $/isnext/[/u/,/v/,/g\//]$.

\startex $/predecessors/[/u/,/g\//]$ is the list of vertices /v/, in /g\//
such that $/isnext/[/v/,/u/,/g\//]$.

\startex $/undir/[/g\//]$ is true if and only if /g\//
is undirected.  That is, if for every
edge from /u/ to /v/ in /g\// there is also and edge from /v/ to /u/.  

\startex $/mkundir/[/g\//]$ is the graph $g↓1$
with the same vertices as /g\//, and  such that
there is an edge from /u/ to /v/ in $g↓1$ if and only if /g\// has either an edge from
/v/ to /u/ or and edge from /u/ to /v/.  

\startex  If /g\// is undirected then
$/delete-vertex/[/v/,/g\//]$  returns a graph $g↓1$ with vertices those of
/g\// omitting /v/, and edges the same as /g\// omitting those connecting /v/ to 
another vertex. 

\startex If /g\// is undirected then
$/complement/[/g\//]$  returns a graph $g↓1$ with vertices the same as /g/, but
vertices /v/ and /w/ are joined by an edge in $g↓1$ if and only if they are not
joined by an edge in /g/.

\startex For any graph /g/, $/reachable/[/u/,/v/,/g\//]$ 
is true if and only if there is a
sequence of vertices $u↓1, u↓2,\ldots,u↓n$ in $g$ with $u = v$, 
$v = u↓n$ and
$isnext[u↓i,u↓{i+1},g]$ for $1≤i≤n\minus 1$.  

\startex For any graph /g/,
$/conn/[/g\//]$ 
is true if and only if the directed graph /g\// is connected in the sense
that every vertex is reachable from every other vertex.  
\item{}
NB:  Graphs may have cycles, so when you are processing a graph
you need to keep track of where you have been in order to avoid an endlessly
looping program.